package com.copa.l53;

/**
 * @author copa
 * @createDate 2022-05-10 17:26
 * @function 动态规划法 每次都听到这个词...但就是不会用...
 */
public class Test3 {
    public int maxSubArray(int[] nums) {
        // 初始化dp数组 dp数组中存储的每个值是：以当前元素结尾的最大的子序列和
        int[] dp = new int[nums.length];
        // 初始值为nums数组第一个元素
        dp[0] = nums[0];
        // result同理
        int result = dp[0];
        // 设定终止条件为遍历nums数组结束
        for (int i = 1; i < nums.length; i++) {
            // 此时dp[i]可选的是 不合并前面的数 || 合并前面的数
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            //  result选择的是本身 || dp[i]的值
            result = Math.max(result, dp[i]);
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        //int[] nums = new int[]{-1, -2};
        System.out.println(new Test3().maxSubArray(nums));
    }
}
